import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/19 15:54
 * @description 堆排序，时间复杂度为O(nlgn)，当用数组A保存堆数据时(下标从0开始)，那么堆的根结点为A[0].
 * 给定一个结点的下标，可以方便的求出父节点、左孩子，右孩子,
 *
 * 下标从0开始：                                      下标从1开始：
 * Parent(i) return (i-1) / 2;                      Parent(i) return i / 2;
 * Left(i) return 2 * i + 1;                        Left(i) return 2 * i;
 * Right(i) return 2 * i + 2;                       Right(i) return 2 * i + 1;
 */
public class HeapSort {

    /**
     * 维护最大堆性质函数，时间复杂度 O(lgn), 使得以下标i为根节点的子树遵循最大堆的性质
     * @param A 数组A
     * @param i 下标i
     */
    public void maxHeapify(int[] A, int i, int heapSize) {
        int left = i * 2 + 1 , right = i * 2 + 2, largest = i;
        if (left < heapSize && A[left] > A[largest]) {
            largest = left;
        }
        if (right < heapSize && A[right] > A[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(A, i, largest);
            maxHeapify(A, largest, heapSize);
        }
    }

    /**
     * 采用自底向上的方法利用 maxHeapify方法 将A[1..n]转换为最大堆。时间复杂度为 O(n)
     * @param A 数组A
     */
    public void buildMaxHeap(int[] A, int heapSize) {
        // 因为 A[len / 2 + 1.. n] 中元素都是树的叶子结点，可看成一个元素的堆，不需要调整，所以从 A[len / 2]开始，自低向上调整
        for (int i = heapSize / 2; i >= 0; i--) {
            maxHeapify(A, i, heapSize);
        }
    }

    /**
     * 堆排序，首先建立初始最大堆，然后每次将A[1]交换到末尾，len - 1, 然后维护最大堆性质
     * @param A 待排序数组A
     */
    public void heapSort(int[] A) {
        int heapSize = A.length;
        buildMaxHeap(A, heapSize);
        for (int i = A.length - 1; i >= 1; --i) {
            swap(A, 0, i);
            --heapSize;
            maxHeapify(A, 0, heapSize);
        }
    }
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
        heapSort.heapSort(A);
        System.out.println(Arrays.toString(A));
    }
}
